Computer graphics are being used today to perform a wide variety of tasks. Many different areas of business, industry, government, education, entertainment, and most recently, the home, are tapping into the enormous and rapidly growing list of applications developed for today's increasingly powerful computer devices. For example, graphical user interfaces have largely replaced textual interfaces as the standard means for user computer interaction.
In most computer graphic systems an image is represented as a raster (an array) of logical picture elements (pixels). A pixel is usually a rectangle, but can be other shapes. The computer graphics system assigns parameter values to each pixel. These parameter values are digital values corresponding to certain attributes of the image (e.g. color, depth, etc.) measured over a small area of the image represented by a pixel. Typically each graphical image is represented by thousands of combined pixels.
In a computer generated image, objects are typically described by "primitives" (usually mathematically described polygons and polyhedra) that define the shape of the primitive, the primitive attributes, and the connectivity and positioning data describing how the primitives fit together. The primitives are subsequently drawn by rendering their pixels in a frame buffer. For example, a point primitive, essentially a circular disc, is rendered as a small group of pixels, the number of which depending upon the display resolution of the computer system's display. A line primitive, often referred to as a vector primitive, is typically rendered as a line of pixels from one point to another, the line being a number of pixels wide depending upon the line's thickness and the display's resolution. An example of a more complex line primitive is a "polyline", which is comprised of two or more line primitives drawn end to end. As the primitives are rasterized onto the array of pixels, the primitives are broken down into small pieces called fragments. Each fragment is the size of a pixel or smaller.
Generally, the fragment or fragments within each pixel determine the image characteristics (e.g., color and the like) of that pixel. The computer system processes the fragments for each pixel of the pixel array to create a graphical image. Some computer systems may include special-purpose processors, each custom tailored to specific graphics functions. The main graphical processing function of the CPU (or special-purpose processors) is to take the specifications of graphical primitives specified by application programs (for example, point primitives and line or polyline primitives) and to render the primitives onto the pixel array in a manner which best represents characteristics of the desired image.
Traditional, low cost graphics rendering systems, however, often generate lines and points in which the edges of the lines or points appear jagged or "aliased". Aliasing artifacts result from the fact that the primitives are drawn in a finite resolution pixel array. More specifically, aliasing artifacts appear when a continuous image is sampled at discreet pixel centers and displayed on a finite resolution screen.
Prior Art FIG. 1A is an illustration of a simple line drawn on a bi-level pixel display. Prior Art FIG. 1B is an expanded view of FIG. 1A. In each column of pixels the line moves through, the color of the pixel nearest the line is set. Each time the line crosses between columns in which the pixels closest to the line are not in the same row, there is a sharp "jag" in the appearance of the line. This characteristic holds true for point primitives and other scan converted primitives, such as polygons. The "jaggies" or "stair stepping" is the result of this "all or nothing" approach to scan conversion in which each pixel is replaced with the primitive's color, or is left unchanged. Stair stepping is a common instance of the phenomenon called "aliasing". The application of techniques that reduce or eliminate aliasing are referred to as "antialiasing" and the rendered images produced using these techniques are said to be "antialiased." Antialiasing removes these aliasing effects from an image and gives the primitive edges a much smoother appearance.
There are many antialiasing techniques published that address the stair stepping problem. These methods are successful to some degree, but have limitations in their implementation. To make the antialiasing process less computationally demanding, many antialiasing techniques utilize look-up tables to implement the filtering functions described above. In such a look-up table technique, a filtered profile of the primitive is stored in the look-up table. The parameters of a fragment, for example, the distance of the center of the fragment from the center of the primitive, are used to index the table and retrieve a corresponding filtered version of the primitive. This filtered version is then rendered. The process of indexing the look-up table with a parameter of a fragment and retrieving the filtered parameter is much less costly than more sophisticated techniques, such as calculating the area of a fragment and blending the fragment using the area.
The problem with the above look-up table method is the fact that the values stored in the table are very much dependent upon the characteristics of the primitive. The look-up table stores the actual profile of a filtered primitive. Typically, the table is loaded with values suited to provide the best antialiasing for the particular characteristics of the primitives being rendered. The quality of antialiasing obtained from this method, depend upon the degree to which the primitives being rendered match the values loaded in the look-up table. For example, where an image includes numerous line primitives and point primitives, the look-up table is loaded with values which yield the best antialiasing for the characteristics of these primitives, for example, the width of the lines and points. So long as primitives having these characteristics are being rendered, this prior art look-up table method yields good results.
The problem with this method, however, is that if the width or position of the line primitives or the size of the point primitives changes, the antialiasing performance of this conventional look-up table method deteriorates. For a table of a given size, for example, if the table is loaded in accordance with antialiasing line primitives of a given width, the table will not properly antialias line primitives which are significantly wider. The antialiasing quality quickly degrades as the width of the line primitives increase, since there are fewer storage locations within the table representing the "fall off" in intensity at the edges of the primitive.
Prior Art FIG. 1C and FIG. 1D graphically depict the problem resulting from changing width. Lines 150 and 151 represent intensity, lines 152 and 153 represent the normalized distance along the antialiased direction of the primitive, and the profiles 155 and 156 represent the intensity of the primitive for a two color bi-level pixel display. Lines 152 and 153 each have a plurality of marks 160 representative of storage locations within a look-up table. Profile 155 is less wide than profile 156. Thus, profile 155 has a much smoother fall off region 170, than the fall off region 171 of profile 156.
Another limitation of this method is the requirement that the table be reloaded in accordance with the particular primitives being rendered. This is too slow for use in more demanding applications. Generating the table on the fly could save main memory but further reduces the performance.
Thus, there is a need for a width independent antialiasing process which is inexpensive to implement, yet highly effective. The required solution should use less memory than prior art antialiasing solutions of comparable quality, and not require repetitive processor intensive calculations. The required solution should be fast enough for demanding applications, without requiring very expensive, high performance graphics hardware for its implementation. Additionally, what is needed is a solution which provides high quality, width independent antialiasing, wherein the antialiasing quality does not degrade as the width of the graphics primitives change.